|
Lupanov's (''k'', ''s'')-representation, named after Oleg Lupanov, is a way of representing Boolean circuits so as to show that the reciprocal of the Shannon effect. Shannon had showed that almost all Boolean functions of ''n'' variables need a circuit of size at least 2''n''''n''−1. The reciprocal is that:
==Definition== The idea is to represent the values of a boolean function ''ƒ'' in a table of 2''k'' rows, representing the possible values of the ''k'' first variables ''x''1, ..., ,''x''''k'', and 2''n''−''k'' columns representing the values of the other variables. Let ''A''1, ..., ''A''''p'' be a partition of the rows of this table such that for ''i'' < ''p'', |''A''''i''| = ''s'' and . Let ''ƒ''''i''(''x'') = ''ƒ''(''x'') iff ''x'' ∈ ''A''''i''. Moreover, let be the set of the columns whose intersection with is . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lupanov representation」の詳細全文を読む スポンサード リンク
|